【Leetcode题解】3-Longest Substring Without Repeating Characters

文章目录

本系列代码见我的Leetcode仓库

tags: [Hash Table,Two Pointers]

在字符串中找到最长的无重复字符的子串，返回它的长度。
这个题的题设要求非常简单，只要出现重复的字符就不行，所以很容易可以想到Hash Table。
HashTable的做法是，从左到右扫描并存储见过的字符，如果遇到该字符已经见过了，则记录当前table容量并与当前最大长度求max，并从左到右删除到该字符为止的已经见过的字符。根据题意可以假设最大长度至少为1，且不会大于26.当原字符串为空时最大长度为0.

从上面HashTable的解法描述中可以提取Two Pointers解法，即设置同向指针left和right，并初始化boolean数组用以表示是否参与当前最长子串计算，boolean数组下标是字符，其作用可以用HashMap代替。
初始left和right指向字符串起点，如果boolean数组right所指向的字符没有参与，则设置为参与并右移，否则计算right-left获得当前长度，并与当前最大长度求max，这之后left左移恢复状态，直到left所指向的字符与right所指向的字符一致。

Two Pointers解法比HashTable解法好的一点是，用boolean数组代替了HashMap，这在运行性能上会好一些，但理论时间复杂度没变，都是O(N)。考虑到隐性假设字符为ASCII字符，范围可控，使用boolean数组做更合适。如果是任意字符，则应该使用HashTable。